//
// Created by SunJingxuan on 2022/4/22.
//
#include <stdio.h>
#include <math.h>
#include <iostream>

#include "SeqList.h"

using namespace std;

bool deleteSeqListMiniValue(SeqList &seqList, int &result) {
    if (seqList.length <= 0) {
        return false;
    }
    result = seqList.data[0];
    int index = 0;
    for (int i = 1; i < seqList.length; i++) {
        int temp = seqList.data[i];
        if (temp < result) {
            result = temp;
            index = i;
        }
    }

    int temp = seqList.data[seqList.length - 1];
    seqList.data[index] = temp;
    seqList.length--;
    return true;
}

void invert(SeqList &seqList) {
    int temp;
    for (int i = 0; i < seqList.length / 2; i++) {
        temp = seqList.data[i];
        seqList.data[i] = seqList.data[seqList.length - 1 - i];
        seqList.data[seqList.length - 1 - i] = temp;
    }
}

void remove(SeqList &seqList, int removeValue) {
    int total = 0;
    for (int i = 0; i < seqList.length; i++) {
        if (seqList.data[i] == removeValue) {
            total++;
        } else {
            seqList.data[i - total] = seqList.data[i];
        }
    }
    seqList.length -= total;
}

bool deleteInterval(SeqList &seqList, int start, int end) {
    if (seqList.length <= 0 || start >= end) {
        return false;
    }
    int head = 0;
    for (; head < seqList.length && seqList.data[head] < start; head++);
    if (head >= seqList.length - 1) {
        return false;
    }
    int tail = head;
    for (; tail < seqList.length && seqList.data[tail] < end; tail++);

    for (; tail < seqList.length; head++, tail++) {
        seqList.data[head] = seqList.data[tail];
    }
    seqList.length = head + 1;
    return true;
}

bool deleteIntervalV2(SeqList &seqList, int start, int end) {
    if (seqList.length <= 0 || start >= end) {
        return false;
    }
    int total = 0;
    for (int i = 0; i < seqList.length; ++i) {
        if (seqList.data[i] > start && seqList.data[i] < end) {
            total++;
        } else {
            seqList.data[i -total] = seqList.data[i];
        }
    }
    seqList.length -= total;
    return true;
}

bool removeDuplicates(SeqList &seqList) {
    if (seqList.length <= 0) {
        return false;
    }
    for (int i = 0; i < seqList.length; i++) {
        int total = 0;
        for (int j = i + 1; j < seqList.length; j++) {
            if (seqList.data[i] == seqList.data[j]) {
                total++;
            } else {
                seqList.data[j - total] = seqList.data[j];
            }
        }
        seqList.length -= total;
    }
    return true;
}

SeqList merge(SeqList seqList1, SeqList seqList2) {
    int s1Length = seqList1.length;
    int s2Length = seqList2.length;
    if (s1Length <= 0 && s2Length <= 0) {
        return initSeqList();
    }
    if (s1Length > 0 && s2Length <= 0) {
        return seqList1;
    }
    if (s1Length <= 0 && s2Length > 0) {
        return seqList2;
    }
    int initLength = s1Length + s2Length;
    SeqList seqList = initSeqList();
    if (seqList.maxSize < initLength) {
        extend(seqList, initLength - seqList.maxSize);
    }

    int counter = 0;
    int i = 0;
    int j = 0;
    while (i < seqList1.length && j < seqList2.length) {
        if (seqList1.data[i] <= seqList2.data[j]) {
            addToIndex(seqList, seqList1.data[i], counter);
            i++;
        } else {
            addToIndex(seqList, seqList2.data[j], counter);
            j++;
        }
        counter++;
    }

    while(i < seqList1.length) {
        addToIndex(seqList, seqList1.data[i], counter);
        i++;
        counter++;
    }

    while (j < seqList2.length) {
        addToIndex(seqList, seqList2.data[j], counter);
        j++;
        counter++;
    }
    return seqList;
}

void reverse(int arr[], int leftIndex, int rightIndex, int arrLength) {
    if (leftIndex >= rightIndex || rightIndex >= arrLength) {
        return;
    }
    for (int i = 0; i <= (rightIndex - leftIndex) / 2; i++) {
        int temp = arr[leftIndex + i];
        arr[leftIndex + i] = arr[rightIndex - i];
        arr[rightIndex - i] = temp;
    }
}

void exchange(int arr[], int leftLength, int rightLength, int arrLength) {
    if (leftLength + rightLength != arrLength) {
        return;
    }
    reverse(arr, 0, leftLength + rightLength - 1, arrLength);
    reverse(arr, 0, rightLength - 1, arrLength);
    reverse(arr, rightLength, leftLength + rightLength - 1, arrLength);
}

int binarySearch(SeqList &seqList, int data) {
    if (seqList.length <= 0) {
        return -1;
    }

    int left = 0;
    int right = seqList.length - 1;
    while (left < seqList.length && right < seqList.length && left < right) {
        int middle = (left + right) >> 1;
        if (seqList.data[middle] == data) {
            return middle;
        } else if (seqList.data[middle] > data){
            addToIndex(seqList, data, middle);
            return -2;
        } else {
            left = middle + 1;
        }
    }
    if (left == right) {
        addToLast(seqList, data);
    }
    return -3;
}

void exchangeValueToAfter(SeqList &seqList, int dataIndex) {
    int temp = seqList.data[dataIndex];
    seqList.data[dataIndex] = seqList.data[dataIndex + 1];
    seqList.data[dataIndex + 1] = temp;
}

int main() {
//    cout << boolalpha;
    SeqList seqList = initSeqList();
    int arr[] = {38, 49, 65, 150, 285, 290, 378, 495, 2985};
    seqList.data = arr;
    seqList.length = 9;
    extend(seqList, 10);
    int result = binarySearch(seqList, 285);
    cout << result << endl;
    if (result >= 0) {
        exchangeValueToAfter(seqList, result);
    }
    print(seqList);
}